|
|
Knihovna pro boolovské funkce v algebraické normální formě
Vasilišin, Maroš ; Mrázek, Vojtěch (oponent) ; Dobai, Roland (vedoucí práce)
Táto bakalárska práca sa zaoberá návrhom a implementáciou knižnice v jazyku C pre manipuláciu Boolovych funkcií v Algebraickej Normálnej Forme. Väčšina existujúcich reprezentácií Boolovych funkcií je založená na binárnych rozhodovacích diagramoch. Algebraická Normálna Forma poskytuje oproti binárnym rozhodovacím diagramom určité výhody, napríklad tú, že sa dá z nej v lineárnom čase určiť Boolova hodnota funkcie. Implementovaná knižnica za pomoci jednoduchých štruktúr poskytuje efektívnu reprezentáciu Boolovej funkcie v programe. Výskumom sme zistili, že reprezentácia pomocou Algebraickej Normálnej Formy má svoj využitie, a v určitých prípadoch dosahuje lepšie výsledky ako reprezentácia pomocou binárnych rozhodovacích diagramov.
|
|
|
New Techniques for Compact Representation of Boolean Functions
Maťufka, Ján ; Holík, Lukáš (oponent) ; Lengál, Ondřej (vedoucí práce)
Binary decision diagrams (BDDs) represent Boolean functions and are extensively used in formal verification, model checking, circuit synthesis in CAD software, etc. With more variables, however, the BDD size grows in the worst case exponentially. The aim of this thesis is to create an automata-based model for compact representation of Boolean functions. To achieve this, tree automata are used. By inserting tree automata with specific properties into the BDD structure, larger repeating patterns can be reduced. This model allows for approximately 10-20 % smaller node counts in tested benchmarks compared to the state-of-the-art models. Using a tree-automata based approach allows for creating custom automata to reduce specific patterns and thus allow for possibly even better results.
|
|
|
Knihovna pro boolovské funkce v algebraické normální formě
Vasilišin, Maroš ; Mrázek, Vojtěch (oponent) ; Dobai, Roland (vedoucí práce)
Táto bakalárska práca sa zaoberá návrhom a implementáciou knižnice v jazyku C pre manipuláciu Boolovych funkcií v Algebraickej Normálnej Forme. Väčšina existujúcich reprezentácií Boolovych funkcií je založená na binárnych rozhodovacích diagramoch. Algebraická Normálna Forma poskytuje oproti binárnym rozhodovacím diagramom určité výhody, napríklad tú, že sa dá z nej v lineárnom čase určiť Boolova hodnota funkcie. Implementovaná knižnica za pomoci jednoduchých štruktúr poskytuje efektívnu reprezentáciu Boolovej funkcie v programe. Výskumom sme zistili, že reprezentácia pomocou Algebraickej Normálnej Formy má svoj využitie, a v určitých prípadoch dosahuje lepšie výsledky ako reprezentácia pomocou binárnych rozhodovacích diagramov.
|
host ::
RSS.